//
//  BackTrackingSolution.cpp
//  leetcode
//
//  Created by Ellie on 2021/2/26.
//  Copyright © 2021 Ellie. All rights reserved.
//

#include "BackTrackingSolution.hpp"


// 剑指 Offer 38. 字符串的排列
// 字符串的全排列
vector<string> BackTrackingSolution::permutation(string s)
{
    vector<string> result;
    permutationstring(s, result, 0);
    return result;
}

void BackTrackingSolution::permutationstring(string& s, vector<string>& result, int startindex)
{
    if(startindex == s.size())
    {
        result.push_back(s);
        return;
    }
    
    for(int i = startindex;i<s.size();i++)
    {
        bool skip = false;
        for(int j = startindex;j<i;j++)
        {
            if(s[j] == s[i])
            {
                skip = true;
                break;
            }
        }
        if(skip)
            continue;
        
        swap(s[startindex], s[i]);
        permutationstring(s, result, startindex + 1);
        swap(s[startindex], s[i]);
    }
}

//46. 全排列，无重复元素
vector<vector<int>> BackTrackingSolution::permute(vector<int>& nums)
{
    vector<vector<int>> result;
    vector<int> track;
    permute(nums, result, track);
    return result;
}

void BackTrackingSolution::permute(vector<int>& nums, vector<vector<int>>& result, vector<int>& track)
{
    int size = nums.size();
    if(track.size() == size)
    {
        result.push_back(track);
        // 已经到了叶子节点，可以直接返回
        // size() = trakc.size() 已经遍历完所有的元素满足全排列的逻辑要求
        return;
    }
    for(int i=0;i<size;i++)
    {
        // 可以直接使用mark解决问题
        if(find(track.begin(), track.end(), nums[i]) != track.end())
            continue;
        track.push_back(nums[i]);
        permute(nums, result, track);
        track.pop_back();
    }
}

//47. 全排列 II 有重复元素
vector<vector<int>> BackTrackingSolution::permuteUnique(vector<int>& nums)
{
    vector<bool> mark = vector<bool>(nums.size(), false);
    vector<vector<int>> result;
    vector<int> track;
    sort(nums.begin(), nums.end());
    permuteUnique(nums, result, track, mark);
    return result;
}

void BackTrackingSolution::permuteUnique(vector<int>& nums, vector<vector<int>>& result, vector<int>& track, vector<bool>& mark)
{
    int size = nums.size();
    if(track.size() == size)
    {
        result.push_back(track);
        return;
    }
    
    // 遍历的时候带着状态
    for(int i=0;i<size;i++)
    {
        if(mark[i])
            continue;
        
        // 剪枝操作
        if(i > 0 && nums[i] == nums[i - 1] && mark[i - 1] == false)
            continue;
        mark[i] = true;
        track.push_back(nums[i]);
        permuteUnique(nums, result, track, mark);
        mark[i] = false;
        track.pop_back();
    }
}

//78. 子集 元素唯一
vector<vector<int>> BackTrackingSolution::subsets(vector<int>& nums)
{
    vector<vector<int>> result;
    // path
    vector<int> track;
    int startindex = 0;
    subsetdfs(nums, result, track, startindex);
    return result;
}

void BackTrackingSolution::subsetdfs(vector<int>& nums, vector<vector<int>>& result, vector<int>& track, int startindex)
{
    result.push_back(track);
    // 非必需
    // 到达子叶节点，所有的元素mark都为true都标记为访问过
    for(int i=startindex;i<nums.size();i++)
    {
        track.push_back(nums[i]);
        subsetdfs(nums, result, track, i + 1);
        track.pop_back();
    }
}

//90. 子集 II 元素可以重复
vector<vector<int>> BackTrackingSolution::subsetsWithDup(vector<int>& nums)
{
    vector<vector<int>> result;
    vector<int> track;
    sort(nums.begin(), nums.end());
    vector<bool> mark = vector<bool>(nums.size(), false);
    subsetsWithDup(nums, result, track, 0, mark);
    return result;
}

void BackTrackingSolution::subsetsWithDup(vector<int>& nums,  vector<vector<int>>& result, vector<int>& track, int startindex, vector<bool>& mark)
{
    result.push_back(track);
    for(int i=startindex;i<nums.size();i++)
    {
        // 剪枝操作
        if(i > 0 && nums[i] == nums[i - 1] && mark[i - 1] == false)
            continue;
        mark[i] = true;
        track.push_back(nums[i]);
        subsetsWithDup(nums, result, track, i + 1, mark);
        mark[i] = false;
        track.pop_back();
    }
}


// 39.组合总和 不好有重复元素
vector<vector<int>> BackTrackingSolution::combinationSum(vector<int>& candidates, int target)
{
    vector<vector<int>> result;
    vector<int> track;
    combinationSum(candidates, result, 0, track, target);
    return result;
}

void BackTrackingSolution::combinationSum(vector<int>& candidates, vector<vector<int>>& result, int startindex, vector<int>& track, int target)
{
    // find valid track path just return
    // 输入都是正整数，== 0 就不用继续遍历深入了
    if(target == 0)
    {
        result.push_back(track);
        return;
    }
    
    if(target < 0)
    {
        return;
    }
    
    for(int i=startindex;i<candidates.size();i++)
    {
        track.push_back(candidates[i]);
        // 一个元素可以多次重复使用
        combinationSum(candidates, result, i, track, target - candidates[i]);
        track.pop_back();
    }
}

//40. 组合总和 II 带有重复元素
vector<vector<int>> BackTrackingSolution::combinationSum2(vector<int>& candidates, int target)
{
    vector<vector<int>> result;
    vector<int> track;
    sort(candidates.begin(), candidates.end());
    vector<bool> mark = vector<bool>(candidates.size(), false);
    bracktrace(candidates, result, track, target, 0, mark);
    return result;
}

void BackTrackingSolution::bracktrace(vector<int>& candidates, vector<vector<int>>& result, vector<int>& track, int target, int startindex, vector<bool>& mark)
{
    if(target == 0)
    {
        result.push_back(track);
        return;
    }
    else if(target < 0)
    {
        return;
    }
    
    for(int i=startindex;i<candidates.size();i++)
    {
        // 剪枝操作
        if(i > 0 && candidates[i] == candidates[i - 1] && mark[i - 1] == false)
            continue;
        mark[i] = true;
        track.push_back(candidates[i]);
        bracktrace(candidates, result, track, target - candidates[i], i + 1, mark);
        mark[i] = false;
        track.pop_back();
    }
}

//77. 组合
vector<vector<int>> BackTrackingSolution::combine(int n, int k)
{
    vector<vector<int>> result;
    vector<int> track;
    combine(n, k, result, track);
    return result;
}

void BackTrackingSolution::combine(int n, int k, vector<vector<int>>& result, vector<int>& track)
{
    // 添加结果的时机，深度为K，track.size() == K 表示深度当前遍历深度为K
    if(track.size() == k)
    {
        result.push_back(track);
        return;
    }
    for(int i=n;i>0;i--)
    {
        track.push_back(i);
        combine(i - 1 , k, result, track);
        track.pop_back();
    }
}

vector<string> BackTrackingSolution::generateParenthesis(int n)
{
    vector<string> result;
    string track = "";
    generateParenthesisRecursion(n, result, track, 0, 0);
    return result;
}

// 回溯算法
// 递归树
// 剪枝的二叉树的中序遍历
void generateParenthesisDFS(int n, vector<string>& result, string& track, int left, int right)
{
    if(left == n && right == n)
    {
        result.push_back(track);
        return;
    }
    
    // 剪枝
    if(left < right)
        return;
    // 二叉树的前序遍历
    // 只有两个选择
    // left + 1 或者 right + 1
    if(left < n)
    {
        track.push_back('(');
        generateParenthesisDFS(n, result, track, left + 1, right);
        track.pop_back();
    }
    
    if(right < n)
    {
        track.push_back(')');
        generateParenthesisDFS(n, result, track , left, right + 1);
        track.pop_back();
    }
}

// 递归算法
void BackTrackingSolution::generateParenthesisRecursion(int n, vector<string>& result, string track, int left, int right)
{
    if(left == n && right == n)
    {
        result.push_back(track);
        return;
    }
    if(left < right)
        return;
    if(left < n)
        generateParenthesisRecursion(n, result, track + "(", left + 1, right);
    if(right < n)
        generateParenthesisRecursion(n, result, track + ")", left , right + 1);
}

